package com.sfx.数据结构.AVLTree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-10-22
 * Time: 15:04
 */

/**
 * 二叉搜索树在插入和删除的时候,节点可能会失衡.
 * 如果在插入和删除的时候通过旋转,始终让二叉搜索树保持平衡,成为自平衡的二叉搜索树
 * AVL是自平衡二叉搜索树的实现之一
 * 如果一个节点的左右孩子,高度差超过1,则此节点失衡,才需要旋转.
 * AVL树的四种失衡情况
 * 1) : LL
 * 2) : RR
 * 3) : LR
 * 4) : RL
 */
public class AVLTree {

    // 1. AVLNode类
    static class AVLNode {
        int key;
        Object value;
        AVLNode left;
        AVLNode right;
        int height = 1;

        public AVLNode(int key) {
            this.key = key;
        }

        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    // 2. 获取AVL树高度
    public int height(AVLNode root) {
        return root == null ? 0 : root.height;
    }

    // 3. 更新AVL树的高度
    public int updateHeight(AVLNode root) {
        if (root == null) return 0;
        return Integer.max(height(root.left), height(root.right)) + 1;
    }

    // 4. 计算平衡因子
    public int bf(AVLNode root) {
        return height(root.left) - height(root.right);
    }

    // 5. AVL的左旋
    public AVLNode leftRotate(AVLNode root) {
        AVLNode rootRight = root.right;
        root.right = rootRight.left;
        rootRight.left = root;
        updateHeight(root);
        updateHeight(rootRight);
        return rootRight;
    }

    // 6. AVL的右旋
    public AVLNode rightRotate(AVLNode root) {
        AVLNode rootLeft = root.left;
        root.left = rootLeft.right;
        rootLeft.right = root;
        updateHeight(root);
        updateHeight(rootLeft);
        return rootLeft;
    }

    // 7. AVL的左右旋(LR)
    // 先将左孩子左旋,再将根节点右旋
    public AVLNode leftRightRotate(AVLNode root) {
        // 先将左孩子左旋
        root.left = leftRotate(root.left);
        // 再将根节点右旋
        return rightRotate(root);
    }

    // 8. AVL的右左旋(RL)
    // 先将右孩孩子右旋,再将根节点左旋
    public AVLNode RightLeftRotate(AVLNode root) {
        // 先将右孩孩子右旋
        root.right = rightRotate(root.right);
        // 再将根节点左旋
        return leftRotate(root);
    }
}